package problem218_The_Skyline_Problem;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/*
 * http://blog.csdn.net/wangjianyu0115/article/details/51037397
 */
public class Solution {
	 public List<int[]> getSkyline(int[][] buildings) {
		 List<int[]> verticalLines=new LinkedList<>();
		 for(int[] b:buildings){
			 verticalLines.add(new int[]{b[0],b[2]});
			 verticalLines.add(new int[]{b[1],-b[2]});
		 }
		 verticalLines.sort(new Comparator<int[]>(){
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]!=o2[0])
					return Integer.compare(o1[0], o2[0]);
				return Integer.compare(o2[1], o1[1]);
			}
		 });
		 PriorityQueue<Integer> maxHeight=new PriorityQueue<>(new Comparator<Integer>(){
			@Override
			public int compare(Integer o1, Integer o2) {
				return Integer.compare(o2, o1);
			}
		 });
		 List<int[]> result=new LinkedList<>();
		 int currentHeight=0,preHeight=0;
		 for(int[] v:verticalLines){
			 if(v[1]>0){
				 maxHeight.add(v[1]);
				 currentHeight=maxHeight.peek();
			 }else{
				 maxHeight.remove(0-v[1]);
				 currentHeight=(maxHeight.peek()==null?0:maxHeight.peek());
			 }
			 if(currentHeight!=preHeight){
				 result.add(new int[]{v[0],currentHeight});
				 preHeight=currentHeight;
			 }
		 }
		 return result;
	 }
}
